#include <stdio.h>
#include <stdlib.h>
#include "graph.h"

int Init(Graph *graph)
{
	graph->MaxVertex = Default_Vertex_Size;
	graph->NumVertex = graph->NumEdge = 0;
	graph->VertexList = malloc(sizeof(datatype) * graph->MaxVertex);
	// graph->VertexList = calloc(Default_Vertex_Size, sizeof(datatype));
	if (graph->VertexList == NULL)
		return -1;
	graph->Edge = malloc(sizeof(int *) * graph->MaxVertex);
	if (graph->VertexList == NULL)
		return -2;
	for (int i = 0; i < graph->MaxVertex; i++)
	{
		graph->Edge[i] = malloc(sizeof(int) * graph->MaxVertex);
		if (graph->Edge[i] == NULL)
			return -3;
	}
	for (int i = 0; i < graph->MaxVertex; i++)
	{
		for (int j = 0; j < graph->MaxVertex; j++)
		{
			if (i == j)
				graph->Edge[i][j] = 0;
			else
				graph->Edge[i][j] = MAX_COST;
		}
	}
	return 0;
}
void Show(Graph *graph)
{
	printf("  ");
	for (int i = 0; i < graph->NumVertex; i++)
		printf("%c ", graph->VertexList[i]);
	printf("\n");
	for (int i = 0; i < graph->NumVertex; i++)
	{
		printf("%c ", graph->VertexList[i]);
		for (int j = 0; j < graph->NumVertex; j++)
		{
			if (graph->Edge[i][j] == MAX_COST)
				printf("%c ", '@'); //约定@在输出时表示无穷大
			else
				printf("%d ", graph->Edge[i][j]);
		}
		printf("\n");
	}
	printf("\n");
}
int InsertVertex(Graph *graph, datatype vertex)
{
	if (graph->NumVertex == graph->MaxVertex)
		return -1;
	graph->VertexList[graph->NumVertex++] = vertex;
	return 0;
}
int GetVertexPosition(Graph *graph, datatype vertex)
{
	for (int i = 0; i < graph->NumVertex; i++)
	{
		if (graph->VertexList[i] == vertex)
			return i;
	}
	return -1;
}
int InsertEdge(Graph *graph, datatype vertex1, datatype vertex2, type_weight cost)
{
	int p1 = GetVertexPosition(graph, vertex1);
	int p2 = GetVertexPosition(graph, vertex2);
	if (p1 == -1 || p2 == -1)
		return -1;
	if (p1 == p2)
		return -2;
	graph->Edge[p1][p2] = graph->Edge[p2][p1] = cost;
	++graph->NumEdge;
	return 0;
}
int RemoveVertex1(Graph *graph, datatype vertex)
{
	int pos = GetVertexPosition(graph, vertex);
	if (pos == -1)
		return -1;
	//顶点列表中的删除顶点后的顶点前移
	for (int i = pos; i < graph->NumVertex - 1; ++i)
		graph->VertexList[i] = graph->VertexList[i + 1];
	//统计删除顶点连接的边数
	int numedge = 0;
	for (int i = 0; i < graph->NumVertex; ++i)
	{
		if (graph->Edge[pos][i])
			numedge++;
	}
	// numedge += graph->Edge[pos][i];
	//行上移
	for (int i = pos; i < graph->NumVertex - 1; ++i)
		for (int j = 0; j < graph->NumVertex; ++j)
			graph->Edge[i][j] = graph->Edge[i + 1][j];
	//列上移
	for (int i = pos; i < graph->NumVertex; ++i)
		for (int j = 0; j < graph->NumVertex; ++j)
			graph->Edge[j][i] = graph->Edge[j][i + 1];
	--graph->NumVertex;
	graph->NumEdge -= numedge;
	return 0;
}
int RemoveVertex2(Graph *graph, datatype vertex)
{
	int pos = GetVertexPosition(graph, vertex);
	if (pos == -1)
		return -1;
	int numedge = 0;
	for (int i = 0; i < graph->NumVertex; ++i)
		numedge += graph->Edge[pos][i];
	//修改顶点列表
	graph->VertexList[pos] = graph->VertexList[graph->NumVertex - 1];
	//行覆盖
	for (int i = 0; i < graph->NumVertex; i++)
		graph->Edge[pos][i] = graph->Edge[graph->NumVertex - 1][i];
	//列覆盖
	for (int i = 0; i < graph->NumVertex; i++)
		graph->Edge[i][pos] = graph->Edge[i][graph->NumVertex - 1];
	--graph->NumVertex;
	graph->NumEdge -= numedge;
	return 0;
}
int RemoveEdge(Graph *graph, datatype vertex1, datatype vertex2)
{
	int p1 = GetVertexPosition(graph, vertex1);
	int p2 = GetVertexPosition(graph, vertex2);
	if (p1 == -1 || p2 == -1)
		return -1;
	if (graph->Edge[p1][p2] == 0) //本来就没有边
		return -2;
	graph->Edge[p1][p2] = graph->Edge[p2][p1] = 0;
	--graph->NumEdge;
	return 0;
}
int GetFirstNeighbor(Graph *graph, datatype vertex)
{
	int pos = GetVertexPosition(graph, vertex);
	if (pos == -1)
		return -1;
	for (int i = 0; i < graph->NumVertex; ++i)
	{
		if (graph->Edge[pos][i] == 1)
			return i;
	}
	return -2;
}
int GetNextNeighbor(Graph *graph, datatype vertex1, datatype vertex2)
{
	int p1 = GetVertexPosition(graph, vertex1);
	int p2 = GetVertexPosition(graph, vertex2);
	if (p1 == -1 || p2 == -1)
		return -1;
	for (int i = p2 + 1; i < graph->NumVertex; i++)
	{
		if (graph->Edge[p1][i] == 1)
			return i; //正确返回结果
	}
	return -1;
}
void DestoryGraph(Graph *graph)
{
	free(graph->VertexList);
	graph->VertexList = NULL;
	for (int i = 0; i < graph->MaxVertex; i++)
		free(graph->Edge[i]);
	free(graph->Edge);
	graph->Edge = NULL;
	graph->MaxVertex = graph->NumVertex = graph->NumEdge = 0;
}
int Prim(Graph *graph, datatype vertex)
{
	int n = graph->NumVertex;
	type_weight *lowcost = malloc(sizeof(type_weight) * n);
	int *mst = malloc(sizeof(int) * n);
	if (lowcost == NULL || mst == NULL)
		return -1;
	int p = GetVertexPosition(graph, vertex);
	if (p == -1)
		return -2;
	for (int i = 0; i < n; i++)
	{
		if (i != p)
		{
			lowcost[i] = graph->Edge[i][p];
			mst[i] = p; //
		}
		else
			lowcost[i] = 0;
	}
	int min, min_index; // lowcost的最小值，最小值的顶点下标
	int begin, end;
	for (int i = 0; i < n - 1; i++)
	{
		min = MAX_COST;
		min_index = -1;
		for (int j = 0; j < n; j++)
		{
			if (lowcost[j] != 0 && lowcost[j] < min) //不为0表示没有加入顶点集合
			{
				min = lowcost[j];
				min_index = j;
			}
		}
		begin = mst[min_index];
		end = min_index;
		printf("%c-->%c : %d\n", graph->VertexList[begin], graph->VertexList[end], graph->Edge[begin][end]);
		lowcost[min_index] = 0;
		for (int i = 0; i < n; i++)
		{
			int cost = graph->Edge[i][min_index];
			if (cost < lowcost[i])
			{
				lowcost[i] = cost;
				mst[i] = min_index;
			}
		}
	}
	return 0;
}

int cmp(const void *a, const void *b)
{
	const Edge *A = a;
	const Edge *B = b;
	return A->cost - B->cost;
}

static void print_edge(Graph *graph, Edge *edge, int k)
{
	for (int i = 0; i < k; i++)
	{
		int v1 = edge[i].x;
		int v2 = edge[i].y;
		printf("edge[%d]: %c-->%c : %d \n", i, graph->VertexList[v1], graph->VertexList[v2], edge[i].cost);
	}
	printf("\n");
}

static void print_father(int *father, int n)
{
	printf("father[]:");
	for (int i = 0; i < n; i++)
		printf("%d ", father[i]);
	printf("\n");
}

int Kruskal(Graph *graph)
{
	int n = graph->NumVertex;

	//初始化边数组
	Edge *edge = malloc(sizeof(Edge) * n * (n - 1) / 2);
	if (edge == NULL)
		return -1;
	int k = 0;
	for (int i = 0; i < n - 1; i++)
		for (int j = i + 1; j < n; j++)
		{
			if (graph->Edge[i][j] != MAX_COST)
			{
				edge[k].x = i;
				edge[k].y = j;
				edge[k].cost = graph->Edge[i][j];
				k++;
			}
		}
	
	//给边数组排序
	qsort(edge, k, sizeof(Edge), cmp);

	//打印排序后的边数组结果(测试用)
	//print_edge(graph, edge, k);

	int *father = malloc(sizeof(int) * n);
	if (father == NULL)
		return -2;
	for (int i = 0; i < n; i++)
		father[i] = i;
	for (int i = 0; i < n; i++)
	{
		// if (!Is_Same(father, edge[i].x, edge[i].y))
		if (!Is_Same_(father, edge[i].x, edge[i].y))
		{
			int v1 = edge[i].x, v2 = edge[i].y;
			printf("%c-->%c : %d \n", graph->VertexList[v1], graph->VertexList[v2], edge[i].cost);

			//将这两个结点标记到同一个连通图中(让它们的父节点相同)
			//Mark_Same(father, edge[i].x, edge[i].y);
			Mark_Same_(father, n, edge[i].x, edge[i].y);

			//打印father数组变化情况(测试用)
			//print_father(father, n);
		}
	}

	free(edge);
	free(father);

	return 0;
}

int Is_Same(int *father, int i, int j)
{
	//老师的写法是不断向上找父，直到找到两个结点的祖宗
	while (father[i] != i)
		i = father[i]; //循环查找一个连通图中的父结点
	while (father[j] != j)
		j = father[j];
	return i == j;
}

void Mark_Same(int *father, int i, int j)
{
	while (father[i] != i)
		i = father[i];
	while (father[j] != j)
		j = father[j];
	father[j] = i;
}
//=========================================================================
// Is_Same_和Mark_Same_函数是我的写法(只有i<j时这样写才成立，因为例如像确定A--C边时，设置father[C] = 0,而确定D--C边时，father[C] = 3.因为前面构造边数组时保证了i<j,所以只有C--D这种情况，那么father[D]就会等于0,使A,C,D在同一个连通图中。其实老师的写法也要保证i<j才成立，以为他写的最后一句：father[j] = i)
int Is_Same_(int *father, int i, int j)
{
	return father[i] == father[j];
}

void Mark_Same_(int *father, int n, int i, int j)
{
	for (int k = 0; k < n; k++)
	{
		if (father[k] == father[j])
			father[k] = father[i];
	}
}